Cuộc chạm trán đầu tiên giữa quân Cờ đen và người Pháp diễn ra khi Jean Dupuis, một thương gia phiêu lưu ngược sông Hồng tìm đường giao thương lên Vân Nam, Trung Quốc. Dupuis trước đó đã đạt được một số thỏa thuận với một viên tướng quân họ Mã ở Vân Nam trong việc cung cấp vũ khí cho đội quân của ông ta, vì khi đó triều đình nhà Thanh đang bận bịu đánh dẹp người Hồi giáo nổi dậy ở cả Vân Nam và Cam Túc. Theo đó Dupuis sẽ tiến hành chở vũ khí, muối, gạo... theo đường sông Hồng vào Vân Nam, đổi lại phía Trung Quốc sẽ nhượng cho Duipuis quyền lợi tham gia khai mỏ đồng và thiếc ở Vân Nam. Tuy nhiên việc giao thương này không được triều đình Đại Nam chấp thuận. Để giải quyết tranh chấp giữa phía Việt Nam và Dupuis, chính quyền Pháp tại Nam kỳ gửi đại úy Francis Garnier (tên Hán Việt: An Nghiệp) ra Hà Nội, nhưng viên đại úy này không những không làm trung gian đàm phán, mà còn hợp lực với người của Dupuis (bao gồm cả quân Cờ vàng) tấn công hạ thành Hà Nội ngày 19 tháng 11 năm 1873, tổng đốc Nguyễn Tri Phương bị thương nặng rồi chết, xung đột tại Bắc kỳ bùng nổ.

Dù chủ lực quân Nam ở Bắc kỳ khi đó vẫn còn tập trung ở thành Sơn Tây, đại úy Garnier vẫn cho xuất quân tiến hành bình định miền châu thổ sông Hồng quanh Hà Nội. Chỉ trong vòng ba tuần, toàn bộ 4 tỉnh miền đồng bằng sông Hồng gồm Hà Nội, Hải Dương, Ninh Bình, Nam Định với 2 triệu dân cư và một số thành lũy đã rơi vào tay đội quân Pháp chỉ chừng 180 người, chỉ huy bởi viên đại úy hải quân chưa tới 35 tuổi[2]. Có thể kể đến trường hợp thành Ninh Bình với 1.700 binh lính hạ vũ khí đầu hàng một toán quân Pháp chỉ có bảy người. Đến giữa tháng 12, Garnier đã có thể quay lại Hà Nội điều hành công việc hành chính. Ông ta cho tổ chức dân quân của những làng công giáo và chọn lựa quan lại cho những vị trí bị bỏ trống.

Triều đình Huế hết sức tức giận vì hành vi tráo trở này, lệnh cho đoàn sứ Đại Nam đang thương nghị ở Sài Gòn phản kháng hành động chiếm thành của F.Garnier, yêu cầu thống đốc Dupré ra lệnh cho Garnier rút quân khỏi thành Hà Nội, đồng thời sai chưởng vệ Phan Đề làm đề đốc, Nguyễn Trọng Hợp làm tán lý cùng với Bùi Ấn Niên làm Khâm phái đưa 1.000 quân từ Huế và Nghệ An ra Bắc tăng cường chống trả quân Pháp. Triều đình ra lệnh cho các quan tỉnh ở các khu vực trọng yếu phải đóng cọc xuống các lòng sông thông với sông Hồng để ngăn chận tàu Pháp. Vua Tự Đức cũng sai Trần Đình Túc, Trương Gia Hội cùng với 2 giáo sĩ Công giáo là giám mục Sovier, linh mục Danzelger ra Hà Nội điều đình với Garnier. Các khâm phái, khâm mạng, các quan cũ ở Hà Nội đều bị cách chức chờ xử phạt.

Ngoài ra triều đình Huế cũng phong cho phò mã Hoàng Kế Viêm làm Tiết chế Bắc kỳ quân vụ, chuẩn bị hành động trả đũa. Hoàng Kế Viêm là chỉ huy cao cấp nhất của các lực lượng quân Nam tại Bắc Kỳ, và cũng cấp trên trực tiếp của Lưu Vĩnh Phúc, nên ông cho gọi Lưu Vĩnh Phúc, khi đó đang đóng tại Hưng Hóa về Sơn Tây làm tiền phong để đánh quân Pháp. Hoàng Kế Viêm vì biết được sự hoang mang tinh thần của quân Nam, nên khích lệ quân Cờ đen bằng cách hứa hẹn thưởng rất nhiều vàng cho mỗi binh lính Pháp bị giết, số lượng vàng sẽ tăng lên theo cấp bậc của kẻ bị giết.

Ngày 18 tháng 12 năm 1873, quân Cờ đen đã về đến Hà Nội và lập trại chỉ cách Hà Nội chừng 10 đến 12 dặm. Ngày 21 tháng 12, nghe tin quân Cờ đen đang tiến về cửa tây thành Hà Nội, Garnier tức khắc lên mặt thành cho pháo khai hỏa về phía đối phương. Sau nửa giờ bắn phá, quân Nam, gồm chừng năm, sáu trăm quân Cờ đen và rất nhiều quân Việt, có voi chiến và nhiều quan lại đi theo, phải rút chạy. Garnier nhanh chóng tiến ra từ cửa đông nam với 18 lính Pháp và chừng một trung đội lính mộ bản xứ truy đuổi. Tuy nhiên chưa đi khỏi thành được bao xa thì khẩu pháo dã chiến bị sa lầy, Garnier bị một toán quân Cờ đen mai phục sẵn đổ ra đâm chết, tại Ô Cầu Giấy.

Garnier bị giết, quân Pháp ở thành Hà Nội lâm vào tình thế hoảng loạn, nếu không nhờ có Linh mục Puginier và Dupuis thì quân Pháp đã bỏ thành theo đường thủy chạy về Sài Gòn. Tuy nhiên cái chết của đại úy Garnier cũng đặt dấu chấm hết cho cuộc phiêu lưu quân sự này tại Bắc Kỳ. Dẫu vậy, cũng chỉ hơn một tháng sau, đại úy Philastre (tên phiên âm: Hoắc Đạo Sanh) được cử ra giải quyết những rắc rối tại Bắc Kỳ đã cho rút hết quân khỏi Hà Nội và trao trả lại Bắc kỳ cho triều đình nhà Nguyễn.

Sau chiến thắng này, Lưu Vĩnh Phúc được thăng lên làm Phó Lãnh binh, chịu sự thống suất của Hoàng Tá Viêm. Các thuộc hạ của Lưu Vĩnh Phúc đều được thưởng quan tước và tiền bạc. Hoàng Tá Viêm sai Lưu Vĩnh Phúc đưa quân rút về chặn ở miền thượng du (Lào Cai), được triều đình Huế cho quyền trông coi việc thông thương và thu thuế ở vùng sông Lô và sông Thao từ Tuyên Quang trở xuống. Tới tháng 10 năm Giáp Tuất (1874), theo lời xin của Hoàng Kế Viêm, Lưu Vĩnh Phúc được thăng chức Quyền Tam Tuyên quân vụ Đề đốc tước vị Lương Nghĩa nam, kiêm coi các đạo và được sai phái đi đánh giặc Cờ vàng.

Triều đình Huế đã tỏ ra rất trọng dụng Lưu Vĩnh Phúc nhưng ông ta vẫn chưa hài lòng. Sáu lần triều đình điều động Lưu Vĩnh Phúc đem quân về Tuyên Quang nhưng ông ta lần nữa không đi, vẫn ở lại Bảo Thắng. Do quan quân nhà Nguyễn bất lực như chính Tự Đức phải thừa nhận: Việc dẹp giặc ở Tuyên Quang lấy đạo Lưu Vĩnh Phúc là chính, nên mặc dù tỏ thái độ bất phụng mệnh, Lưu Vĩnh Phúc và quân Cờ đen trước sau vẫn được nhà Nguyễn để tâm dùng. Nắm được điểm yếu ấy của triều đình Huế, Lưu Vĩnh Phúc luôn ra điều kiện mặc cả về mức ban thưởng quan tước và tiền bạc cho mình và bộ thuộc sau mỗi trận đánh, thậm chí cả việc xin truy phong quan tước cho cha mẹ mình.

Mùa đông năm 1881-1882, Lưu Vĩnh Phúc lần đầu tiên trở lại Trung Quốc thăm viếng quê nhà. Khi đi ông ta là một kẻ tội phạm bị truy nã, khi về ông được đón tiếp long trọng như một anh hùng, không những là quan nhà Nguyễn mà còn mang phẩm hàm võ quan của nhà Thanh. Lưu Vĩnh Phúc mua đất đai ở làng cũ, dự định đến một ngày nào đó sẽ về dưỡng già, nhưng các biến động tại Bắc kỳ liên tiếp diễn ra, và Lưu Vĩnh Phúc lại được triệu tập trở lại Bắc kỳ.